P3147 [USACO16OPEN]262144

---

DP好题，状态比较难想

f[i][j]表示将位置为i的数合成数字j所需要达到的最右点

初始f[i][a[i]]=i+1

因为合并距离都是2幂次，所以转移可以用类似倍增的思想

循环j套i

$$f[i][j]=f[f[i][j-1]][j-1]$$

若f[i][j]不为0则说明i位置上j是可行的

最后统计可行j的最大值即可

---

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

const int N=262150;
int n,ans,f[N][60];

signed main(){
    read(n);
    for(int i=1,x;i<=n;i++) f[i][read(x)]=i+1; //初始都在自己右边
    for(int j=2;j<=58;j++)
        for(int i=1;i<=n;i++){
            if(f[i][j]==0) f[i][j]=f[f[i][j-1]][j-1]; //类似倍增跳过去
            if(f[i][j]>0) ans=j; //可行就更新答案
        }
    write(ans);
}